\subsection{Постановка задачи}

\subsubsection{Разрабатываемый ассемблер}
В Проблемной лаборатории вычислительной биологии АУ РАН \footnote{bioinf.spbau.ru}, под руководством Павла Певзнера \footnote{Professor, University of California at San Diego} и Максима Алексеева \footnote{Assistant professor, University of South Carolina}, с февраля 2011 года, ведется разработка нового ассемблера, использующего подход, основанный на графе де Брюина.

В силу достаточно жестких требований к производительности и потребляемой памяти, разработку ассемблера было решено вести на языке C++.

Этот проект нацелен сразу на два направления, еще не охваченные существующими продуктами.

\begin{itemize}
\item \emph{Работа с данными секвенирования, полученными по единственной клетке.} 

Значительная часть видов бактерий не поддается клонированию в условиях лаборатории. Раньше секвенировать такие бактерии было невозможно, но сравнительно недавно 
появились технологии, позволяющие получать достаточное для сборки количество ридов по нескольким или даже всего лишь одной клетке (single cell sequencing technologies). К сожалению, использование этих технологий приводит к получению ридов, крайне неравномерно покрывающих геном (разброс кратности покрытия может составлять десятки тысяч). С такими входными данными не справляется ни один из существующих ассемблеров. 

Для того, чтобы ассемблировать риды, полученные по single cell технологиям секвенирования, необходимо разработать принципиально новые подходы к обработке графа де Брюина.

\item \emph{Сборке больших геномов с использованием ``бесконтекстного'' подхода.}

На данный момент, наиболее узкое место всех современных ассемблеров, нацеленных на сборку больших геномов (прежде всего, геномов млекопитающих) --- это размер потребляемой оперативной памяти. К примеру, для \textit{de novo} сборки человеческого генома по коротким ридам ассемблеру SOAP \textit{de novo}, требуется супер-компьютер с 512Gb оперативной памяти.

Одним из наиболее перспективных подходов к сборке больших геномов, является так называемый ``бесконтекстный'' подход. Основная его идея в том, чтобы попробовать отказаться от хранения и использования конкретных последовательностей нуклеотидов при построении и анализе графа де Брюина (формально, используемый там граф не является графом де Брюина, но очень похож на него по топологической структуре). 

Ни один из существующих ассемблеров данный подход не использует. По нашим предварительным оценкам, его использование позволит снизить требования к потребляемой оперативной памяти в десятки раз и позволит перенести сборку больших геномов с супер-компьютеров с сотнями гигабайт оперативной памяти (который, кстати говоря, есть не в любой исследовательской лаборатории) на мощные сервера.

\end{itemize}

Являясь сотрудником упомянутой лаборатории, я принимаю активное участие в разработке нового ассемблера.

Было решено разбить проект на три фазы.
\begin{itemize}
\item Реализовать хороший ассемблер для бактериальных геномов, использующий известные и не раз опробованные методы, а также новый подход к разрешению повторов.
\item Реализовать бесконтекстный подход и приспособить ассемблер к сборке генома млекопитающих.
\item Детально исследовать проблемы, возникающие при сборке по данным от single cell sequencing и разработать методы их преодоления.
\end{itemize}

Пока проект находится в первой фазе, и наш ближайший планы --- разработать просто хороший ассемблер для бактериальных геномов. 
Но при этом было принято решения сразу же проектировать ассемблер максимально гибко, чтобы при переходе к следующей фазе проекта не пришлось бы переделывать все с нуля.

\subsubsection{Цели работы}
В рамках проекта, я занимался разработкой библиотеки для построения и обработки сжатого графа де Брюина.

Результатом работы должна была стать библиотека, послужащая базой для для нового ассемблера.

Основными целями моей работы были:
\begin{itemize}
\item \emph{Разработка удобной, расширяемой библиотеки для работы с графом де Брюина.} 

Библиотека должна предоставлять удобные средства для разработки новых алгоритмов обработки и анализа графа. 

\item \emph{Разработка алгоритмов обнаружения и устранения ошибочных участков графа.} 

В рамках нашего проекта, важным требованием к этим алгоритмам, является наличие режима работы, не использующего конкретные последовательности нуклеотидов. Это нужно для того, чтобы их можно было применить к графу, реализующему ``бесконтекстный'' подход. 
\end{itemize}
